package swardToOffer.struct_4_tree;

import java.util.*;

// 面试题32（三）：之字形打印二叉树
// 题目：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺
// 序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印， 其他行以此类推。
// 思路，和分行打印一样，只是增加一个当前所在行的判断，并基于判断结果按如下规律插入辅助队列中
// 如果当前行为奇数行，则尾插，如果当前行为偶数行，则头插
public class PrintTreesInZigzag {
    void printTreeInZigzag(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) tmp.addLast(node.val); // // 奇数层 -> 队列尾部
                else tmp.addFirst(node.val); // 偶数层 -> 队列头部
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        res.forEach(System.out::println);
    }

    public static void main(String[] args) {
        PrintTreesInZigzag Main = new PrintTreesInZigzag();
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8};
        TreeNode root = TreeUtil.build(nums, 0, 7);
        new PrintTreesInLines().printTreeInLines(root);
        System.out.println();
        Main.printTreeInZigzag(root);

    }

}
